package BasicClass.Four;

import java.util.HashSet;

public class Test_Twelfth {
    public static void main(String[] args) {

    }

    /**
     * 输入两个无环的单链表，找出它们的第一个公共结点。
     * （注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
     * @param pHead1
     * @param pHead2
     * @return
     */

    //方法1：使用Hash表
    //思路：
    //将一个链表循环一遍，并将每个节点放置在Hash表中
    //循环第二个链表，每过一个节点，查询一下Hash表中
    //第一个查询到的节点就是相交的第一个节点
//    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
//        HashSet<ListNode> hashSet = new HashSet<>();
//        while (pHead1 != null){
//            hashSet.add(pHead1);
//            pHead1 = pHead1.next;
//        }
//        while (pHead2 != null){
//            if (hashSet.contains(pHead2)){
//                break;
//            }
//            pHead2 = pHead2.next;
//        }
//        return pHead2;
//    }

    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    //方法2：使用双指针
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        int size = 0;
        ListNode cur1 = pHead1;
        while (cur1.next != null){
            size++;
            cur1 = cur1.next;
        }
        ListNode cur2 = pHead2;
        while (cur2.next != null){
            size--;
            cur2 = cur2.next;
        }
        if (cur1 != cur2){
            return null;
        }
        if(size>0){
            while (size>0){
                pHead1 = pHead1.next;
                size--;
            }
        }else if(size<0){
            while (size<0){
                pHead2 = pHead2.next;
                size++;
            }
        }
        while (pHead1 != null){
            if (pHead1 == pHead2){
                break;
            }
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return pHead1;
    }
}
